#include <iostream>
#include <cstring>
#include <string>

using namespace std;

typedef long long int64;

int	main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int m, n;
		string n_str;
		cin >> n_str >> m;
		while (n_str.size() > 1 && n_str[0] == '0') n_str = n_str.substr(1);
		if (n_str.size() > 9)
			n = 1000000000;
		else 
			n = atoi(n_str.c_str());

		if (n > m) n = m;
		int k = 1, s = 1;
		for (int i = 1; i <= n; ++i)
		{
			k = int64(k) * i % m;
			s = s + k;
			if (s >= m) s -= m;
		}
		cout << s % m << endl;
	}
	return 0;
}